阅读下列说明和C代码,回答问题1和问题2,将解答填入答题纸的对应栏内。
【说明】
某公司购买长钢条,将其切割后进行出售。切割钢条的成本可以忽略不计,钢条的长度为整英寸。已知价格表p,其中pi(i=1,2,...,m)表示长度为i英寸的钢条的价格。现要求解使销售收益最大的切割方案。
求解此切割方案的算法基本思想如下:
假设长钢条的长度为n英寸,最佳切割方案的最左边切割段长度为i英寸,则继续求解剩余长度为n-i 英寸钢条的最佳切割方案。考虑所有可能的i,得到的最大收益rn对应的切割方案即为最佳切割方案。rn的递归定义如下:
rn =max1≤ i ≤n(pi +rn-i)
对此递归式,给出自顶向下和自底向上两种实现方式。
【C代码】
/* 常量和变量说明 n:长钢条的长度 p[]:价格数组 */ #define LEN 100 int Top_Down_ Cut_Rod(int p[],int n) { /*自顶向下*/ int r=0; int i; if(n == 0) { return 0; } for (i=1; (1) ;i++) { int tmp = p[i]+Top_Down_Cut_Rod(p,n-i); r=(r>=tmp)?r:tmp; } return r; } int Bottom_Up_Cut_Rod(int p[],int n) { /*自底向上*/ int r[LEN]= { 0 } ; int temp=0; int i,j; for (j=1;j<=n;j++) { temp=0; for (i=1; (2) ;i++) { temp= (3) ; } (4) ; } return r[n]; }
请先在App中激活(应用市场搜“软考真题”)
2019-09-17
请先在App中激活(应用市场搜“软考真题”)
2019-05-15
请先在App中激活(应用市场搜“软考真题”)
2019-11-05
请先在App中激活(应用市场搜“软考真题”)
2019-05-25
请先在App中激活(应用市场搜“软考真题”)
2019-11-04
请先在App中激活(应用市场搜“软考真题”)
2021-05-28
请先在App中激活(应用市场搜“软考真题”)
2019-05-12